#include <stdio.h>

//排序算法
//1、冒泡排序
void BubbleSort(int *a,int len)
{
    //冒泡冒n-1次
    for(int i = 0; i < len - 1; i++)
    {
        int flag = 0;
        for(int j = 0; j < len - 1 -i; j++)
        {
            if(a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;
            }
        }
        //循环一次后，数列已经有序，不在需要再次循环比较
        if(flag == 0)
        {
            break;
        }
    }  
}

//2、插入排序
void InsertSort(int *a,int len)
{
    for(int i = 1; i < len; i++)
    {
        int temp = a[i];
        int j = i;
        for(j = i; j > 0; j--)
        {
            if(a[j - 1] > temp)
            {
                a[j] = a[j - 1];
            }
            else
            {
                break;
            }
        }
        a[j] = temp;
    }
}

//3、选择排序:每次选择剩下数列中最小的一个数放到最前面
void ChooseSort(int *a,int len)
{
    for(int i = 0; i < len; i++)
    {
        int min = i;
        for(int j = i + 1; j < len; j++)
        {
            if(a[j] < a[min])
            {
                min = j;
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

//4、选择排序的优化:每次选最小的和最大的
void ChooseSort2(int *a,int len)
{
    int left = 0;
    int right = len - 1;
    while(left < right)
    {
        int min = left;
        int max = right;
        for(int i = left; i <= right; i++)
        {
            if(a[i] < a[min])
            {
                min = i;
            }
            if(a[i] > a[max])
            {
                max = i;
            }
        }
        int temp = a[left];
        a[left] = a[min];
        a[min] = temp;

        if(max == left)
        {
            max = min;
        }

        temp = a[right];
        a[right] = a[max];
        a[max] = temp;

        left++;
        right--;
    }
}

//5、快速排序---nlogn
void FastSort(int *a,int start,int end)
{
    //终止排序
    if(start >= end)
    {
        return;
    }
    int temp = a[start];
    int left = start;
    int right = end;

    while(left < right)
    {
        while(left < right && a[right] > temp)
        {
            right--;
        }
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }
        while(left < right && a[left] < temp)
        {
            left++;
        }
        if(left < right)
        {
            a[right] = a[left];
            right--;
        }
    }
    a[left] = temp;
    //递归排序
    FastSort(a,start,left-1);
    FastSort(a,right+1,end);
}

//顺序查找
int FindElementByIndex(int *a,int len,int target)//----------o(n)
{
    for(int i = 0;i < len; i++)
    if(a[i] == target)
    {
        return i;
    }
    return -1;
}

//二分查找--------------(logn) 必须是有序的
int BinaryFind(int *a,int len,int target)
{
    int left = 0;
    int right = len - 1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2; //若写为(left + right)/2  要考虑int是否会溢出
        if(a[mid] == target)
        {
            return mid;
        }
        if(a[mid] > target)
        {
            right = mid - 1;
        }
        if(a[mid] < target)
        {
            left = mid + 1;
        }
    }
    return -1;
}



void PrintArray(int *a,int len)
{
    for(int i = 0; i < len; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

int main()
{
    int a[] = {98,6,16,7,3,34,76,1};
    //BubbleSort(a,sizeof(a)/4);
    //InsertSort(a,sizeof(a)/4);
    //ChooseSort(a,sizeof(a)/4);
    //ChooseSort2(a,sizeof(a)/4);
    FastSort(a,0,sizeof(a)/4 - 1);
    //printf("%d\n",FindElementByIndex(a,sizeof(a)/4,7));
    printf("%d\n",BinaryFind(a,sizeof(a)/4,7));
    //PrintArray(a,sizeof(a)/4);
    return 0;
}